0621. 任务调度器【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 贪心

1. 📝 题目描述

• leetcode

给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表，用字母 A 到 Z 表示，以及一个冷却时间 n。每个周期或时间间隔允许完成一项任务。任务可以按任何顺序完成，但有一个限制：两个 相同种类 的任务之间必须有长度为 n 的冷却时间。

返回完成所有任务所需要的 最短时间间隔。

---

示例 1：

输入：tasks = ["A","A","A","B","B","B"], n = 2
输出：8

解释：
在完成任务 A 之后，你必须等待两个间隔。
对任务 B 来说也是一样。在第 3 个间隔，A 和 B 都不能完成，所以你需要待命。
在第 4 个间隔，由于已经经过了 2 个间隔，你可以再次执行 A 任务。

示例 2：

输入：tasks = ["A","C","A","B","D","B"], n = 1
输出：6

解释：
一种可能的序列是：A -> B -> C -> D -> A -> B。
由于冷却间隔为 1，你可以在完成另一个任务后重复执行这个任务。

示例 3：

输入：tasks = ["A","A","A","B","B","B"], n = 3
输出：10

解释：
一种可能的序列为：A -> B -> idle -> idle -> A -> B -> idle -> idle -> A -> B。
只有两种任务类型，A 和 B，需要被 3 个间隔分割。
这导致重复执行这些任务的间隔当中有两次待命状态。

---

提示：

• 1 <= tasks.length <= 10^4
• tasks[i] 是大写英文字母
• 0 <= n <= 100

2. 🎯 s.1 - 贪心

c

int leastInterval(char* tasks, int tasksSize, int n) {
    int cnt[26] = {0};
    for (int i = 0; i < tasksSize; i++) cnt[tasks[i] - 'A']++;
    int maxCnt = 0, maxNum = 0;
    for (int i = 0; i < 26; i++) {
        if (cnt[i] > maxCnt) { maxCnt = cnt[i]; maxNum = 1; }
        else if (cnt[i] == maxCnt) maxNum++;
    }
    int res = (maxCnt - 1) * (n + 1) + maxNum;
    return res > tasksSize ? res : tasksSize;
}

js

/**
 * @param {character[]} tasks
 * @param {number} n
 * @return {number}
 */
var leastInterval = function (tasks, n) {
  const cnt = new Array(26).fill(0)
  for (const t of tasks) cnt[t.charCodeAt(0) - 65]++
  const maxCnt = Math.max(...cnt)
  const maxNum = cnt.filter((c) => c === maxCnt).length
  return Math.max(tasks.length, (maxCnt - 1) * (n + 1) + maxNum)
}

py

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        cnt = Counter(tasks)
        max_cnt = max(cnt.values())
        max_num = sum(1 for v in cnt.values() if v == max_cnt)
        return max(len(tasks), (max_cnt - 1) * (n + 1) + max_num)

• 时间复杂度：$O(n)$，其中 n 是任务总数
• 空间复杂度：$O(1)$，只用固定大小 26 的数组

算法思路：

• 统计出现次数最多的任务数量 maxCnt 及有多少种任务达到最大次数 maxNum
• 最少时间 = max(任务总数, (maxCnt - 1) * (n + 1) + maxNum)
• 前者对应任务足够填满的情况，后者对应需要插入空闲时间的情况